class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (prices.size() <= 1) {
            return 0;
        }
        int n = prices.size();
        vector<int> left(n);
        vector<int> right(n);

        left[0] = 0;
        int minValue = prices[0];
        for (int i = 1; i < n; ++i) {
            left[i] = max(left[i - 1], prices[i] - minValue);
            minValue = min(minValue, prices[i]);
        }

        right[n - 1] = 0;
        int maxValue = prices[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            right[i] = max(right[i + 1], maxValue - prices[i]);
            maxValue = max(maxValue, prices[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, left[i] + right[i]);
        }
        return ans;
    }
};
